package com.liu.algorithm.sort.counting;

/**
 * 意大利面排序
 * 首先，取一把未煮的意大利面，对于数组中的每一个数字，剪一根对应长度的意大利面条，用这根面条代表这个数字。
 * 用一只手拿着这一把面条，将其竖着立在桌子上，保证每一根的底部都碰到桌面。另一只手从面条的上方缓缓下落。
 * 显然，这只手碰到的第一根面条就是最长的，将其取出放至首位。重复此过程直至所有的面条取完，数字就完成了排序。
 *
 * @author liubo
 */
public class LeetcodeSpaghettiSort {
    public static void spaghettiSort(int[] arr) {
        // 假设数字大小都在 1～9 之间，准备一把长度在 1～9cm 之间的面条，用面条的长度记录数字大小。
        // 注：为了便于理解，新建长度为 10 的数组，只使用数组的 1～9 位，不使用数组的第 0 位
        int[] spaghettiLength = new int[10];
        // 遍历数组中的每个数字
        for (int element : arr) {
            // 将每个数字的大小反映成面条的长短
            spaghettiLength[element]++;
        }
        // 右手从高处落下，碰到的第一根面条对应的数字就是最大的数字，重复此过程直到排序完成
        for (int i = 9, index = 0; i >= 1; i--) {
            while (spaghettiLength[i] != 0) {
                spaghettiLength[i]--;
                arr[index++] = i;
            }
        }
    }
}
